package sorted;

import java.util.Arrays;
import java.util.Random;

/**
 * 归并排序（递归和，非递归）
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-02-17
 */
public class MergeSort {

    // 递归写法
    public static void fun(int[] arr) {
        if (arr == null || arr.length < 1) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }

    public static void merge(int[] arr, int L, int mid, int R) {
        int[] temp = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= R) {
            temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            temp[i++] = arr[p1++];
        }
        while (p2 <= R) {
            temp[i++] = arr[p2++];
        }
        for (int j = 0; j < temp.length; j++) {
            arr[L + j] = temp[j];
        }
    }

    // 非递归写法
    public static void fun1(int[] arr) {
        if (arr == null || arr.length < 1) {
            return;
        }
        int N = arr.length;
        int step = 1;
        while (step < N) {
            int L = 0;
            while (L < N) {
                int M = 0;
                if (L + step - 1 < N) {
                    M = L + step - 1;
                } else {
                    M = N - 1;
                }
                // M
                if ((M + 1) == N) {
                    merge(arr, L, M, N - 1);
                    break;
                }
                int R = 0;

                if (M + step < N) {
                    R = M + step;
                } else {
                    R = N - 1;
                }
                merge(arr, L, M, R);
                L = R + 1;
            }
            step = step * 2;
        }
    }

    public static void main(String[] args) {
        int count = 10;
        Random random = new Random();
        for (int i = 0; i < count; i++) {
            int size = random.nextInt(20);
            int[] arr = new int[size];
            for (int j = 0; j < size; j++) {
                arr[j] = random.nextInt(100);
            }
            System.out.println("初始化前数组：" + Arrays.toString(arr));
//            fun(arr);
            fun1(arr);
            System.out.println("初始化后数组：" + Arrays.toString(arr));
        }
    }

}
